package offer.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * @author DengYuan2
 * @create 2021-03-17 19:04
 */
public class NC45 {
    public static void main(String[] args) {
        NC45 n = new NC45();
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        t1.left=t2;
        t1.right=t3;
        t2.left=t4;
        t2.right=t5;
        int[][] res = n.threeOrders(t1);
        for (int i = 0; i < res.length; i++) {
            System.out.println(Arrays.toString(res[i]));
        }
    }

    public int[][] threeOrders (TreeNode root) {

        //前序遍历
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        ArrayList<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()){
            TreeNode parent = stack.pop();
            list.add(parent.val);
            if (parent.right!=null){
                stack.push(parent.right);
            }
            if (parent.left!=null){
                stack.push(parent.left);
            }
        }
        int[][] res = new int[3][list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[0][i]=list.get(i);
        }
        //中序遍历
        list.clear();
        TreeNode cur = root;
        int idx=0;
        while (cur!=null || !stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            cur=stack.pop();
            res[1][idx++]=cur.val;
            cur=cur.right;
        }
        //后序遍历
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode parent = stack.pop();
            res[2][--idx]=parent.val;
            if (parent.left!=null){
                stack.push(parent.left);
            }
            if (parent.right!=null){
                stack.push(parent.right);
            }
        }
        return res;

    }
}
